package xyz.scootaloo.oj.iq

import org.junit.Test
import xyz.scootaloo.console.app.support.Tester
import xyz.scootaloo.oj.ds.helper.CollectionHelper
import java.util.*

/**
 * 哨兵
 * 未完成
 * @author flutterdash@qq.com
 * @since 2021/4/18 10:02
 */
class M1723 {

    /**
     * 1, 0, 1      0, 1, 0
     * 0, 0, 1  =>  1, 2, 0
     * 0, 0, 1      2, 3, 0
     */
    fun findSquare(matrix: Array<IntArray>): IntArray {
        val row = matrix.size
        val column = matrix[0].size
        val dpArray = Array(size = row, init = { IntArray(column) })

        // init first row
        for (c in 0 until column)
            if (matrix[0][c] == 0)
                dpArray[0][c] = 1

        for (r in 1 until row) {
            for (c in 0 until column) {
                if (matrix[r][c] == 0) {
                    dpArray[r][c] = dpArray[r - 1][c] + 1
                }
            }
        }

        val stack = Stack<Int>()
        val res = IntArray(3)
        val tmp = IntArray(3)
        for (r in 0 until row) {
            getMaxArea(dpArray, r, stack, tmp)
            if (tmp[2] > res[2]) {
                res[0] = tmp[0]
                res[1] = tmp[1]
                res[2] = tmp[2]
            }
        }

        return if (res[2] == 0) IntArray(0) else res
    }

    private fun getMaxArea(dpArray: Array<IntArray>, row: Int, stack: Stack<Int>, tmp: IntArray): IntArray {
        clear(tmp)
        val dpRow = dpArray[row]
        val weights = IntArray(dpRow.size + 2)
        for (idx in 1 until (weights.size - 1))
            weights[idx] = dpRow[idx - 1]

        stack.clear()
        stack.push(0)
        for (idx in 1 until weights.size) {
            val currentWeight = weights[idx]
            while (currentWeight < weights[stack.peek()]) {
                val curHei = weights[stack.pop()]
                val curWid = idx - stack.peek() - 1
                val minWei = Math.min(curHei, curWid)
                if (minWei > tmp[2]) {
                    set(tmp, row - minWei + 1, idx - curWid - 1, minWei)
                }
            }
            stack.push(idx)
        }

        return tmp
    }

    private fun clear(res: IntArray) {
        res[0] = 0
        res[1] = 0
        res[2] = 0
    }

    private fun set(res: IntArray, r: Int, c: Int, side: Int = 1) {
        res[0] = r
        res[1] = c
        res[2] = side
    }

    @Test
    fun testc() {
        Tester.createTest(this::findSquare)
            .addCase(arrayOf(
                intArrayOf(1, 0, 1),
                intArrayOf(0, 0, 1),
                intArrayOf(0, 0, 1),
            ), intArrayOf(1, 0, 2))
            .addCase(arrayOf(
                intArrayOf(0, 1, 1),
                intArrayOf(1, 0, 1),
                intArrayOf(1, 1, 0),
            ), intArrayOf(0, 0, 1))
            .addCase(arrayOf(
                intArrayOf(1, 1, 1),
                intArrayOf(1, 1, 1),
                intArrayOf(1, 1, 1),
            ), IntArray(0))
            .addCase(arrayOf(
                intArrayOf(0, 0, 1),
                intArrayOf(0, 0, 1),
                intArrayOf(1, 1, 0),
            ), intArrayOf(0, 0, 2))
            .addCase(arrayOf(
                intArrayOf(0, 0, 0),
                intArrayOf(0, 0, 0),
                intArrayOf(0, 0, 0),
            ), intArrayOf(0, 0, 3))
            .addCase(arrayOf(
                intArrayOf(0, 1, 0),
                intArrayOf(1, 0, 1),
                intArrayOf(0, 1, 0)
            ), intArrayOf(0, 0, 1))
            .setMatcher(CollectionHelper::intListMatch)
            .testAndShow()
    }

}
